public class MyLinkedList {
    ListNode head;
    ListNode tail;
    static class ListNode{
        int val;
        ListNode prev;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }
    public MyLinkedList() {
        this.head = new ListNode(-1);
        this.tail = new ListNode(-1);
        this.head.next = this.tail;
        this.tail.prev = this.head;

    }


    public int get(int index) {
        if(index<0){
            return -1;
        }
        ListNode cur = this.head.next;
        while(index>0&&cur!=this.tail){
            cur = cur.next;
            index--;
        }
        if(cur==this.tail){
            return -1;
        }else{
            return cur.val;
        }

    }

    public void addAtHead(int val) {
        ListNode cur = new ListNode(val);
        this.head.next.prev = cur;
        cur.next = this.head.next;
        this.head.next = cur;
        cur.prev = this.head;
    }

    public void addAtTail(int val) {
        ListNode cur = new ListNode(val);
        this.tail.prev.next = cur;
        cur.prev = this.tail.prev;
        cur.next = this.tail;
        this.tail.prev = cur;

    }
//在链表中的第 index 个节点之前添加值为 val  的节点。
    public void addAtIndex(int index, int val) {
        if(index<0){
            return ;
        }else if(index==0){
            addAtHead(val);
            return ;
        }
        ListNode cur = this.head.next;
        while(cur!=this.tail&&index>0){
            cur = cur.next;
            index--;
        }
        //如果等于链表的长度，尾插
        if(cur==this.tail&&index==0){
            addAtTail(val);
            return ;
            //如果大于链表的长度，不进行操作
        }else if(cur==this.tail&&index>0){
            return ;
        }else {
            ListNode tem = new ListNode(val);
            cur.prev.next = tem;
            tem.prev = cur.prev;
            tem.next = cur;
            cur.prev = tem;
        }
    }
//如果索引 index 有效，则删除链表中的第 index 个节点。
    public void deleteAtIndex(int index) {
        if(index<0){
            return ;
        }
        ListNode cur = this.head.next;
        while(cur!=this.tail&&index>0){
            cur = cur.next;
            index--;
        }
        if(cur==this.tail){
            return;
        }else{
            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
        }

    }
    public void display(){
        ListNode cur = this.head.next;
        while(cur!=this.tail){
            System.out.print(cur.val+"->");
            cur = cur.next;
        }
        System.out.println("null");
    }
}
